package leetcode.editor.cn;

//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
//复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 3000 
// -10⁵ <= nums[i] <= 10⁵ 
// 
// Related Topics 数组 双指针 排序 👍 4650 👎 0

import java.util.*;

//Java：【15】 - 三数之和
public class ThreeSum_15{
    public static void main(String[] args) {
        Solution solution = new ThreeSum_15().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3) return new ArrayList<>();
        Arrays.sort(nums);
        List<List<Integer>> res =new ArrayList<>();
        for (int k = 0; k < nums.length-2; k++) {
            if(nums[k]>0) break; // k是最小的肯定只能为负数
            if(k>0 && nums[k]==nums[k-1]) continue; // 跳过重复值
            int i = k+1, j = nums.length-1;
            while (i<j){
                int tmp =nums[k]+nums[i]+nums[j];
                if(tmp<0){ // 和小于0，说明i可以大些
                    while(i<j && nums[i] == nums[++i]); // 跳过i值相同的
                }else if(tmp>0){ // 和大于0， 说明j可以小些
                    while(i<j && nums[j] == nums[--j]); // 跳过j值相同的
                }else{
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[k]);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    res.add(list);
                    while(i<j && nums[i] == nums[++i]);
                    while(i<j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
